package Merge;

public class QuickSort {

    public void sort(int[] arr){
        recursion(arr,0,arr.length - 1);
    }

    public void recursion(int[] arr,int left,int right){
        if (left >= right){
            return;
        }
        int mid = getMid(arr,left,right);
        recursion(arr,left,mid - 1);
        recursion(arr,mid + 1,right);
    }


    //双边快速排序
    public int getMid(int[] arr,int left,int right){
        int i = left;
        int j = right;
        int temp = arr[left];
        while (i < j){
            while (i < j && arr[j] > temp){
                j--;
            }
            while (i < j && arr[i] <= temp){
                i++;
            }
            swap(arr,i,j);

        }
        swap(arr,i,left);
        return i;
    }

    private void swap(int[] arr,int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
